package es.deusto.ingenieria.is.search.heuristic;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import es.deusto.ingenieria.is.formulation.Operator;
import es.deusto.ingenieria.is.formulation.Problem;
import es.deusto.ingenieria.is.formulation.State;
import es.deusto.ingenieria.is.search.Node;

public class Astar extends HeuristicSearchMethod {

	public Astar(EvaluationFunction function) {
		super(function);
	}

	@Override
	public Node search(Problem problem, State initialState) {

		List<Node> frontier = new ArrayList<Node>();
		List<State> generatedStates = new ArrayList<State>();
		List<State> expandedStates = new ArrayList<State>();
		Node firstNode = null;
		List<Node> successorNodes = null;
		boolean solutionFound = false;
		frontier.add(new Node(initialState));
		while (!solutionFound && !frontier.isEmpty()) {
			firstNode = frontier.remove(0);
			if (problem.isFinalState(firstNode.getState())) {
				solutionFound = true;
			} else {
				successorNodes = this.expand(firstNode, problem,
						generatedStates, expandedStates);
				if (successorNodes != null && !successorNodes.isEmpty()) {
					frontier.addAll(successorNodes);
					Collections.sort(frontier);
				}
			}
		}
		if (solutionFound) {

			return firstNode;

		} else {

			return null;
		}

	}

	protected List<Node> expand(Node node, Problem problem,
			List<State> generatedStates, List<State> expandedStates) {
		List<Node> successorNodes = new ArrayList<Node>();
		Node successorNode = null;

		State currentState = null;
		State successorState = null;

		if (node != null && problem != null) {
			currentState = node.getState();
			generatedStates.remove(currentState);
			expandedStates.add(currentState);

			if (currentState != null) {

				for (Operator operator : problem.getOperators()) {
					successorState = operator.apply(currentState);
					if (successorState != null) {
						successorNode = new Node(successorState);
						successorNode.setOperator(operator.getName());
						successorNode.setParent(node);
						successorNode.setDepth(node.getDepth() + 1);
						successorNode.setH(this.getEvaluationFunction()
								.calculateH(successorNode));
						successorNode.setG(this.getEvaluationFunction()
								.calculateG(successorNode));
						successorNodes.add(successorNode);
						generatedStates.add(successorState);
					}
				}
			}
		}
		return successorNodes;
	}
}
